package com.cong.sort.shell;

/**
 * 希尔排序
 * created on 2021-03-19 by cong
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {11, 5, 8, 77, 66, 55, 32};
        print(arr);
        sort2(arr);
        System.out.println();
        print(arr);

    }

    /**
     *
     * @param arr
     */
    public static void sort(int[] arr) {
        for (int i = arr.length/2; i >0 ; i/=2) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j; k >i-1 ; k-=i) {
                    if (arr[k]<arr[k-i]){
                        swap(arr,k,k-i);
                    }
                }
            }
        }

    }
    /**
     * Knuth序列
     * @param arr
     */
    public static void sort2(int[] arr) {
        int h =1;
        while (h<= arr.length/3){
            h= h*3+1;
        }
        for (int i = h; i >0 ; i=(i-1)/3) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j; k >i-1 ; k-=i) {
                    if (arr[k]<arr[k-i]){
                        swap(arr,k,k-i);
                    }
                }
            }
        }

    }
    
    static void swap(int[] arr, int source, int target) {
        int temp = arr[target];
        arr[target] = arr[source];
        arr[source] = temp;
    }

    static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
